The present invention concerns a digital signal coding device and method. It also concerns a decoding method and device corresponding to the coding method and device.
The purpose of coding is to compress the signal, which enables the digital signal to be transmitted, or respectively stored, thus reducing the transmission time or transmission rate, or respectively reducing the memory space used.
The invention is situated in the field of compression of digital signals with loss.
In a first aspect, breaking down a signal into frequency sub-bands before compressing it is known. The breakdown consists of creating, from the signal, a set of sub-bands which each contain a limited range of frequencies. The sub-bands can be of different resolutions, the resolution of a sub-band being the number of samples per unit length used for representing this sub-band. In the case of a digital image signal, a frequency sub-band of this signal can itself be considered to be an image, that is to say a bidimensional table of numerical values.
It should be noted that breaking down a signal into frequency sub-bands does not create any compression in itself, but makes it possible to decorrelate the signal so as to eliminate redundancy therefrom prior to the compression proper. The sub-bands are thus coded more effectively than the original signal.
A known method of coding a digital signal, in this case of a digital image, includes three main steps. The image is first of all broken down by a transformation into frequency sub-bands, then a scalar quantization of the coefficients thus obtained is performed. The quantized indices are finally coded by entropic coding without loss.
This method affords a high degree of compression of the signal. However, the ratio between the degree of compression and the coding error leaves room for improvement.
In the first aspect, the present invention aims to remedy the drawbacks of the prior art by providing a digital signal compression device and method which offers a high ratio of compression to distortion.
In second and third aspects, a known method of coding a digital signal, in this case of a digital image, is trellis coded quantization, which is described for example in the article entitled xe2x80x9cTrellis Coded Quantization of Memoryless and Gauss-Markov Sourcesxe2x80x9d by M. W. Marcellin and T. R. Fischer, which appeared in IEEE Transactions on Communications, Vol 38, Number 1, January 1990, as well as in the article xe2x80x9cUniversal Trellis Coded Quantizationxe2x80x9d by J. H. Kasner, M. W. Marcellin and B. R. Hunt, available by Internet at the address http://vail.ece.arizona.edu/Publications.html.
This method has the advantage of minimising the quantization error by virtue of the use of trellis coding.
In addition, in order to improve the ratio of compression to distortion, the inventors combined this method with another coding mode. In this case, blocks of the signal to be coded are allocated one or other coding mode, so as to select for each block the most appropriate coding mode, that is to say the one providing the highest ratio of compression to distortion.
Block here means a set of coefficients extracted from the signal in order to form a vector.
Coding by trellis coded quantization is applied to a series of blocks. For the coding to be optimal, it is necessary for the series to be fixed and known in advance. This means that, in order to allocate this mode to a given block in an optimum fashion, it would be necessary to know in advance all the blocks to which this code is allocated, and therefore to know the result of the allocation. There is therefore a difficulty in optimally allocating the coding modes to the blocks and consequently in obtaining the highest possible ratio of compression to distortion.
In the second aspect, the present invention aims to remedy the drawbacks of the prior art by providing a digital signal compression device and method which offers a high ratio of compression to distortion.
In the third aspect, the present invention aims to remedy the drawbacks of the prior art by providing a digital signal compression device and method which make it possible to allocate the trellis coded quantization coding mode to blocks formed in the signal, with great simplicity of implementation.
In a fourth aspect, the present invention aims to improve the first aspect of the invention, by applying a preprocessing between the step of breaking down into sub-bands and the coding step proper.
In the first aspect, the invention proposes a digital signal coding method, including the analysis of the signal in order to separate the pertinent information and the non-pertinent information, then the coding of the non-pertinent information according to a first coding mode which offers a high degree of compression, and coding of the pertinent information according to a second coding mode which limits distortion.
To this end, the invention proposes a digital signal coding method including a step of analysing the digital signal into a plurality of frequency sub-bands distributed in at least two different frequency bands, at least one first sub-band having a lower frequency and at least one second sub-band having a higher frequency,
characterised in that it includes, for each second sub-band, the steps of:
dividing the second sub-band into blocks,
selecting first blocks which are to be coded by setting to a predetermined value and second blocks which are to be coded by trellis coded quantization, according to a selection criterion,
linking the second blocks selected at the previous step in order to form a series of blocks,
coding the series of blocks by trellis coded quantization of a series of coefficients extracted from the second blocks of the second sub-band.
Correlatively, the invention proposes a digital signal coding device including means of analysing the digital signal into a plurality of frequency sub-bands distributed in at least two different frequency bands, at least one first sub-band having a lower frequency and at least one second sub-band having a higher frequency,
characterised in that it includes:
means of dividing each second sub-band into blocks,
means of selecting first blocks which are to be coded by setting to a predetermined value and second blocks which are to be coded by trellis coded quantization, according to a selection criterion,
means of linking the second blocks selected at the previous step in order to form a series of blocks,
means of coding the series of blocks by trellis coded quantization of a series of coefficients extracted from the second blocks of the second sub-band.
The breakdown into frequency sub-bands makes it possible to separate the pertinent information from the non-pertinent information. The non-pertinent information is then coded by setting to the predetermined value, which requires a nil transmission rate. Compression of the non-pertinent information is maximal.
It is thus possible to give a higher transmission rate to the pertinent information, present in the second blocks, which is thus coded more precisely. Distortion of the pertinent information is minimal, by virtue of the linking of the second blocks and their coding by trellis coded quantization.
Overall, the ratio of compression to distortion obtained is high.
The predetermined value is for example nil, so that, at decoding, blocks are constructed whose coefficients are nil.
According to a preferred characteristic, for each of the blocks the selection step includes the coding of the block by setting to the predetermined value and by a second coding mode, the comparison of the two coding modes according to the selection criterion and the selection of the coding by setting to the predetermined value if the block coded by setting to the predetermined value satisfies the selection criterion.
The selection is simple and rapid to implement. For example, the second coding mode is a scalar quantization of the coefficients of the block, or the second coding mode is a trellis coded quantization of a series of coefficients extracted from the blocks of the second sub-band. The latter case enables the structure of the coding device to be simplified, since the selection means then use the same coding as the means of coding the second blocks.
According to a preferred characteristic, the selection criterion minimises a weighted sum of the transmission rate and of the coding error caused by the coding of the block under consideration.
According to another preferred characteristic, an indicator is associated with each block in order to indicate whether or not the block under consideration is coded by setting to the predetermined value.
According to another preferred characteristic, the said at least one first sub-band is coded according to a third coding mode.
The coding device has means adapted to implement the above characteristics.
The invention also concerns a method of decoding a coded digital signal, the said signal including coded representations of blocks formed in frequency sub-bands of the original signal, each coded representation including at least one indicator representing a coding by setting to a predetermined value or a coding by trellis coded quantization of a series of coefficients extracted from blocks, characterised in that it includes the steps of:
reading the value of the indicator of each of the blocks,
decoding representations by formation of reconstructed blocks, all the coefficients of which have the predetermined value, or by trellis coded dequantization of the series of coefficients, as a function of the value of the respective indicator of each of the blocks.
Correlatively, the invention concerns a device for decoding a coded digital signal, the said signal including coded representations of blocks formed in frequency sub-bands of the original signal, each coded representation including at least one indicator representing a coding by setting to a predetermined value or a coding by trellis coded quantization of a series of coefficients extracted from blocks, characterised in that it has:
means of reading the value of the indicator of each of the blocks,
means of decoding representations by formation of reconstructed blocks, all the coefficients of which have the predetermined value, or by trellis coded dequantization of the series of coefficients, as a function of the value of the respective indicator of each of the blocks.
The decoding method and device make it possible to reconstruct the signal, for example in a receiving apparatus corresponding to a sending apparatus in which the signal has been coded according to the invention.
In the second aspect, the invention proposes an iterative optimisation of the allocation of coding by trellis coded quantization and of another coding mode, to blocks formed in a digital signal.
More precisely, the invention concerns a digital signal coding method, characterised in that it includes the steps of:
dividing the signal into blocks,
updating, at which a coding cost for each of the blocks is calculated, for at least a first coding mode and for a coding mode by trellis coded quantization,
allocating one of the coding modes to each of the blocks, according to an allocation criterion depending on the coding cost,
reiterating the updating and allocation steps, so as to satisfy a convergence criterion.
Correlatively, the invention proposes a digital signal coding device, characterised in that it has:
means of dividing the digital signal into blocks,
updating means, adapting to calculate a coding cost for each of the blocks, for at least a first coding mode and for a coding mode by trellis coded quantization,
means of allocating one of the coding modes to each of the blocks, according to an allocation criterion depending on the coding cost,
the updating and allocation means being adapted to be used iteratively, so as to satisfy a convergence criterion.
The method and device according to the invention make it possible to obtain a high ratio of compression to distortion. This is because, by virtue of the updating and allocation iterations, the invention improves the allocation of the coding modes to the blocks. The latter are thus coded in a more suitable fashion.
According to a preferred characteristic, the coding cost of each block is a weighted sum of the coding rate and error of the block under consideration. This coding cost is simple to implement and gives satisfactory results.
According to another preferred characteristic, at a given iteration, the calculation of the coding cost for the coding mode by trellis coded quantization of any block under consideration, to which the coding mode by trellis coded quantization has been allocated, includes the steps of:
linking the blocks to which the trellis coded quantization coding mode has been allocated, in order to form a series of blocks,
coding the series of blocks by trellis coded quantization of a series of coefficients extracted from the linked blocks,
extracting the coding rate and error from the block under consideration.
This calculation makes it possible to precisely determine the coding cost as defined.
According to a preferred characteristic, at a given iteration, the coding cost for the trellis coded quantization coding mode for any block under consideration, to which the first coding mode was allocated, is the coding cost for the trellis coded quantization coding mode for the block calculated at the time of the last iteration during which the trellis coded quantization coding mode was allocated to the block.
According to a preferred characteristic, the allocation criterion minimises the coding cost. Allocating a coding mode to a block amounts to comparing two coding costs and selecting the coding mode associated with the lowest cost.
According to a preferred characteristic, the coding method also includes an initialisation step at which the trellis coded quantization coding mode is allocated to each of the blocks. This step makes it possible to calculate a first trellis coded quantization coding cost for each of the blocks.
According to a preferred characteristic, the convergence criterion is satisfied when the same coding modes are respectively allocated to the same blocks at two successive iterations of the allocation step. This criterion is reliable whilst being simple to implement.
According to a preferred characteristic, an indicator is associated with each block in order to indicate which coding mode is allocated to each block. This indicator is then used at the time of decoding of the blocks.
According to a preferred characteristic, the first coding mode is a setting of the coefficients of the block to a predetermined value. This coding mode has the advantages of being a good approximation of the blocks containing little information, being very simple to implement and of having an associated coding rate which is nil.
The invention also concerns a method of decoding a coded digital signal, the said signal including coded representations of blocks formed in the original signal, each coded representation including at least one indicator representing either a first coding mode or a trellis coded quantization coding mode, characterised in that it includes the steps of:
reading the value of the indicator,
decoding the coded representations, according to the value of the respective indicator.
Correlatively, the invention concerns a device for decoding a coded digital signal, the said signal including coded representations of blocks formed in the original signal, each coded representation including at least one indicator representing either a first coding mode or a trellis coded quantization coding mode, characterised in that it includes:
means of reading the value of the indicator,
means of decoding the coded representations, according to the value of the respective indicator.
The decoding method and device enable the signal to be reconstructed, for example in a receiving apparatus corresponding to a sending apparatus in which the signal was coded according to the invention.
The invention also relates to a digital signal processing apparatus, having means of implementing the coding method, or the decoding method, or including the coding device, or the decoding device, as disclosed above.
The advantages of the coding device, of the decoding device and method and of this digital signal processing apparatus are identical to those of the coding method previously disclosed.
In the third aspect, the invention proposes an iterative optimisation of the allocation of coding by trellis coded quantization and of another coding mode, to blocks formed in a digital signal.
More precisely, the invention concerns a digital signal coding method, characterised in that it includes the steps of:
dividing the signal into blocks,
updating, at which a coding cost for each of the blocks is calculated, for at least a first coding mode and for a coding mode by scalar quantization,
allocating one of the coding modes to each of the blocks, according to an allocation criterion depending on the coding cost,
reiterating the updating and allocation steps, so as to satisfy a convergence criterion,
linking the blocks to which the scalar quantization coding mode was allocated, in order to form a series of blocks,
coding the series of blocks by trellis coded quantization of a series of coefficients extracted from the blocks in the series.
Correlatively, the invention proposes a digital signal coding device, characterised in that it has:
means of dividing the digital signal into blocks,
updating means, adapting to calculate a coding cost for each of the blocks, for at least a first coding mode and for a coding mode by scalar quantization,
means of allocating one of the coding modes to each of the blocks, according to an allocation criterion depending on the coding cost,
the updating and allocation means being adapted to be used iteratively, so as to satisfy a convergence criterion,
means of linking the blocks to which the scalar quantization coding mode was allocated, in order to form a series of blocks,
means of coding the series of blocks by trellis coded quantization of a series of coefficients extracted from the blocks in the series.
By virtue of the method and device according to the invention, the allocation of scalar quantization to the blocks constitutes a good approximation of the allocation of the trellis coded quantization coding mode and has the advantage of being simple and rapid to implement.
In addition, the method and device according to the invention make it possible to obtain a high ratio of compression to distortion. This is because, by virtue of the updating and allocation iterations, the invention improves the allocation of the coding modes to the blocks. The latter are thus coded in a more suitable fashion.
According to a preferred characteristic, the coding cost of each block is a weighted sum of the coding rate and error of the block under consideration. This coding cost is simple to implement and gives satisfactory results.
According to a preferred characteristic, at a given iteration, the calculation of the coding cost for the coding mode by scalar quantization of any block under consideration, includes the steps of:
grouping the blocks to which the scalar quantization coding mode has been allocated, in order to form a group of blocks,
coding the group of blocks by scalar quantization,
determining an entropic coder adapted to the distribution of the symbols resulting from the scalar quantization of the blocks of the group,
entropic coding of the quantized block under consideration, by means of the previously determined entropic coder,
extracting the coding rate of the block under consideration.
According to a preferred characteristic, at a given iteration, the calculation of the coding cost for the scalar quantization coding mode for any block under consideration includes the step of determining the distortion associated with the coding of the block under consideration by scalar quantization.
The coding rate and distortion for the scalar quantization coding mode are determined with calculations which are simple and rapid to make.
According to another preferred characteristic, the allocation criterion minimises the coding cost. Allocating a coding mode to a block amounts to comparing two coding costs and selecting the coding mode associated with the lowest cost.
According to a preferred characteristic, the method also includes an initialisation step at which the scalar quantization coding mode is allocated to each of the blocks. This step makes it possible to calculate a first scalar quantization coding cost for each of the blocks.
According to a preferred characteristic, the convergence criterion is satisfied when the same coding modes are respectively allocated to the same blocks at two successive iterations of the allocation step. This criterion is reliable whilst being simple to implement.
According to a preferred characteristic, an indicator is associated with each block in order to indicate which coding mode is allocated to each block. This indicator is then used at the time of decoding of the blocks.
According to a preferred characteristic, the first coding mode is a setting of the coefficients of the block to a predetermined value. This coding mode has the advantages of being a good approximation of the blocks containing little information, of being very simple to implement and of having an associated coding rate which is nil.
The invention also relates to a digital signal processing apparatus, having means of implementing the coding method, or including the coding device, as disclosed above.
The advantages of the coding device and of this digital signal processing apparatus are identical to those of the coding method previously disclosed.
In the fourth aspect, a preprocessing is applied between the step of breaking down into sub-bands and the coding step proper.
The invention proposes a digital signal coding method including the analysis of the signal in order to separate the pertinent information and the non-pertinent information, and then the preprocessing of the non-pertinent information according to a first preprocessing mode, and preprocessing of the pertinent information according to a second preprocessing mode. The preprocessing modes are determined so as to facilitate the coding of the preprocessed signal.
To this end, the invention proposes a digital signal coding method including a step of analysing the digital signal into a plurality of frequency sub-bands distributed in at least two different frequency bands, at least one first sub-band having a lower frequency and at least one second sub-band having a higher frequency,
characterised in that it includes, for each second sub-band, the steps of:
dividing the second sub-band into blocks,
selecting first blocks and second blocks, according to a selection criterion,
preprocessing the first blocks by applying a first preprocessing mode,
preprocessing the second blocks by applying a second preprocessing mode,
coding the sub-band including the preprocessed blocks, by applying a third coding mode.
Correlatively, the invention proposes a digital signal coding device including means of analysing the digital signal into a plurality of frequency sub-bands distributed in at least two different frequency bands, at least one first sub-band having a lower frequency and at least one second sub-band having a higher frequency,
characterised in that it includes:
means of dividing each second sub-band into blocks,
means of selecting first blocks and second blocks, according to a selection criterion,
means of preprocessing the first blocks by applying a first preprocessing mode,
means of preprocessing the second blocks by applying a second preprocessing mode,
means of coding the sub-band including the preprocessed blocks, by applying a third coding mode.
The method and device according to the invention afford a high ratio of compression to distortion.
This is because the selection separates the pertinent or useful information from the non-pertinent or parasitic information, such as background noise for example. The preprocessing then reduces the influence of the non-pertinent information, by virtue of which the coding is more effective.
Overall, the ratio of compression to distortion obtained is high.
According to a preferred characteristic, for each of the blocks, the selection step includes:
the coding of the block by a first coding mode and by a second coding mode,
the comparison of the two coding modes according to the selection criterion, and
selecting the first and second blocks according to the result of the comparison.
The selection is simple to implement.
According to another preferred characteristic, the selection criterion minimises a weighted sum of the transmission rate and coding error caused by the coding of the block in question.
This criterion makes it possible to distinguish the blocks containing pertinent information and the blocks containing parasitic information.
According to preferred characteristics, the first coding mode is a setting to zero of the coefficients of the block, and the second coding mode is a scalar quantization of the coefficients of the block. The second coding mode can also be a coded trellis quantization of a series of coefficients extracted from the block, or a vector quantization of the block.
These coding modes are simple and rapid to implement.
According to other preferred characteristics, the first preprocessing mode is a zeroing of the coefficients of the block, and the second preprocessing mode is identity. Thus the parasitic information is replaced by zeroed blocks, whilst the pertinent information is not modified.
According to a preferred characteristic, the third coding mode is identical to the second coding mode, which simplifies the implementation of the invention.
According to preferred characteristics, the third coding mode is a trellis coded quantization of a series of coefficients extracted from the preprocessed blocks, or a scalar quantization of the sub-band, or also a vector quantization of the sub-band.
According to another preferred characteristic, the said at least one first sub-band is coded according to a fourth coding mode.
The coding device has means adapted to implement the above characteristics.
The invention also concerns an information storage means, which can be read by a computer or by a microprocessor, whether or not integrated into the device, optionally removable, and which stores a program implementing the coding or respectively decoding method.
The characteristics and advantages of the present invention will emerge more clearly from a reading of a preferred embodiment illustrated by the accompanying drawings, in which:
FIG. 1 depicts a block diagram of a first embodiment of a digital signal coding device according to the invention;
FIG. 2 depicts a circuit for breaking down into frequency sub-bands, included in the device of FIG. 1;
FIG. 3 depicts a digital image to be coded by the coding device of FIG. 1;
FIG. 4 depicts an image broken down into sub-bands by the circuit of FIG. 2;
FIG. 5 depicts an image broken down into sub-bands and then divided into blocks;
FIG. 6 depicts a circuit for coding by trellis coded quantization, included in the device of FIG. 1;
FIG. 7 depicts a block diagram of a first embodiment of a decoding device according to the invention;
FIG. 8 depicts an algorithm for coding a digital signal according to the first embodiment of the invention;
FIG. 9 depicts an algorithm for decoding a digital signal according to the first embodiment of the invention;
FIG. 10 is a block diagram of a second embodiment of a digital signal coding device according to the invention;
FIG. 11 is a block diagram of a second embodiment of a decoding device according to the invention;
FIG. 12 is a digital signal coding algorithm according to the second embodiment of the invention;
FIG. 13 is a digital signal decoding algorithm according to the second embodiment of the invention;
FIG. 14 is a block diagram of a third embodiment of a digital signal coding device according to the invention;
FIG. 15 is a block diagram of a third embodiment of a decoding device according to the invention;
FIG. 16 is a digital signal coding algorithm according to the third embodiment of the invention;
FIG. 17 is a digital signal decoding algorithm according to the third embodiment of the invention;
FIG. 18 is a block diagram of a fourth embodiment of a digital signal coding device according to the invention;
FIG. 19 is a block diagram of a fourth embodiment of a decoding device according to the invention;
FIG. 20 is a coding algorithm for a digital signal according to the fourth embodiment of the invention;
FIG. 21 is a decoding algorithm for a digital signal according to the fourth embodiment of the invention.